COMP3411 Tutorial – Week 7
Planning
Question 1 (Exercise 6.1 from Poole & Macworth)
Features:
RLoc – Rob’s location RHC – Rob has coffee SWC – Sam wants coffee MW – Mail is waiting RHM – Rob has mail
Actions:
mc – move clockwise
mcc – move counterclockwise puc – pickup coffee
dc – deliver coffee
pum – pickup mail
dm – deliver mail
Consider the planning problem from the lectures.
(a) Give the STRIPS representations for the pick up mail (pum) and deliver mail (dm) actions. (b) Give the feature-based representation of the MW and RHM features.
Solution
(a) The pickup mail action (pum) is defined using STRIPS by: Preconditions: RLoc = mr ∧ mw
Effects: [¬mw, rhm]
The deliver mail action (dm) is defined using STRIPS by:
Preconditions: RLoc = off ∧ rhm Effects: [¬rhm]
(b) The MW feature can be axiomatised by defining when MW = true (written as mw): mw’ ← mw ∧ Action ≠ pum
The RHM feature can be axiomatised by defining when RHM = true (written as rhm): rhm’ ← Action = pum
rhm’ ← rhm ∧ Action ≠ dm
Question 2
Formulate the blocks world using STRIPS planning operators. The actions are stack (move one block to the top of another) and unstack (move one block to the table). The robot can hold only one block at a time.
To simplify the world, assume the only objects are the blocks and the table, and that the only relations are the on relation between (table and) blocks and the clear predicate on table and blocks. Also assume that it is not possible for more than one block to directly support another block (and vice versa).
Solution
stack(A, B):
Preconditions: clear(A) ∧ clear(B)
Effects: on(A, B) ∧ ¬ clear(B) unstack(A):
Preconditions: clear(A) ∧ on(A, B)
Effects: on(A, Table) ∧ clear(B) ∧ ¬on(A, B)
Note: The Effects could also be written as an addles contain only the positive literals and the delete list, containing only the negative literals.
Question 3
The Sussman anomaly, shown below, is a simple planning problem that could not be solved by the early linear planners. Show how a partial order planner would solve this problem with the blocks world operators defined above.
Solution
• The nonlinear planner introduces the two actions stack(B, C) and stack(A, B).
• The clear(A) precondition of stack(A,B) does not hold in the initial state, so unstack(C) is added to the plan.
• Because stack(A,B) deletes clear(B), which is a precondition of stack(B,C), stack(B,C) must be before stack(A,B).
• For the same reason, unstack(C) must be before move(B, C).
• The plan is therefore unstack(C), stack(B, C), stack(A, B).